<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>有序数组的平方 | ShuangChenYue</title>
    <meta name="generator" content="VuePress 1.9.9">
    <link rel="icon" href="https://cdn.jsdelivr.net/gh/cmty256/imgs-blog@main/logo/白云.38zbldnhh180.jpg">
    <meta name="description" content="满招损，谦受益">
    <meta name="keywords" content="专注于Cpp语言的旅行者">
    
    <link rel="preload" href="/assets/css/0.styles.3fffbd7d.css" as="style"><link rel="preload" href="/assets/js/app.c23950b3.js" as="script"><link rel="preload" href="/assets/js/2.4615a819.js" as="script"><link rel="preload" href="/assets/js/65.1a70901c.js" as="script"><link rel="prefetch" href="/assets/js/10.5712a6b9.js"><link rel="prefetch" href="/assets/js/100.2b9c7044.js"><link rel="prefetch" href="/assets/js/101.b7031f7a.js"><link rel="prefetch" href="/assets/js/102.f5f3d542.js"><link rel="prefetch" href="/assets/js/11.64978825.js"><link rel="prefetch" href="/assets/js/12.4672093d.js"><link rel="prefetch" href="/assets/js/13.cda96393.js"><link rel="prefetch" href="/assets/js/14.0924c9b3.js"><link rel="prefetch" href="/assets/js/15.838c84fd.js"><link rel="prefetch" href="/assets/js/16.eb504b4c.js"><link rel="prefetch" href="/assets/js/17.10770306.js"><link rel="prefetch" href="/assets/js/18.47c8e9dc.js"><link rel="prefetch" href="/assets/js/19.9ccbab29.js"><link rel="prefetch" href="/assets/js/20.cfe64352.js"><link rel="prefetch" href="/assets/js/21.08ded76b.js"><link rel="prefetch" href="/assets/js/22.30a8a7ba.js"><link rel="prefetch" href="/assets/js/23.e55cce19.js"><link rel="prefetch" href="/assets/js/24.7def6d62.js"><link rel="prefetch" href="/assets/js/25.2b56efaf.js"><link rel="prefetch" href="/assets/js/26.3b3ea698.js"><link rel="prefetch" href="/assets/js/27.5c60f91f.js"><link rel="prefetch" href="/assets/js/28.2bbf1597.js"><link rel="prefetch" href="/assets/js/29.05fbd423.js"><link rel="prefetch" href="/assets/js/3.c7255874.js"><link rel="prefetch" href="/assets/js/30.54f725db.js"><link rel="prefetch" href="/assets/js/31.3e5c530d.js"><link rel="prefetch" href="/assets/js/32.f8ecda14.js"><link rel="prefetch" href="/assets/js/33.3bef3da7.js"><link rel="prefetch" href="/assets/js/34.0e1b1990.js"><link rel="prefetch" href="/assets/js/35.21acae61.js"><link rel="prefetch" href="/assets/js/36.744eb2f7.js"><link rel="prefetch" href="/assets/js/37.15a6e5e0.js"><link rel="prefetch" href="/assets/js/38.0fe5adf3.js"><link rel="prefetch" href="/assets/js/39.d873f04b.js"><link rel="prefetch" href="/assets/js/4.8844c7c6.js"><link rel="prefetch" href="/assets/js/40.a9c0394e.js"><link rel="prefetch" href="/assets/js/41.bd1b72f7.js"><link rel="prefetch" href="/assets/js/42.8c5ba50f.js"><link rel="prefetch" href="/assets/js/43.1c2fbec0.js"><link rel="prefetch" href="/assets/js/44.2601ff73.js"><link rel="prefetch" href="/assets/js/45.be6d6650.js"><link rel="prefetch" href="/assets/js/46.43c49e4e.js"><link rel="prefetch" href="/assets/js/47.915bfbea.js"><link rel="prefetch" href="/assets/js/48.2eab3613.js"><link rel="prefetch" href="/assets/js/49.80f28ebf.js"><link rel="prefetch" href="/assets/js/5.d85ca603.js"><link rel="prefetch" href="/assets/js/50.7807e666.js"><link rel="prefetch" href="/assets/js/51.1d274389.js"><link rel="prefetch" href="/assets/js/52.509cdcc1.js"><link rel="prefetch" href="/assets/js/53.aecfe03c.js"><link rel="prefetch" href="/assets/js/54.aa316fa4.js"><link rel="prefetch" href="/assets/js/55.b8aeead5.js"><link rel="prefetch" href="/assets/js/56.3e7b5654.js"><link rel="prefetch" href="/assets/js/57.3d08056f.js"><link rel="prefetch" href="/assets/js/58.00820ba6.js"><link rel="prefetch" href="/assets/js/59.4d4be159.js"><link rel="prefetch" href="/assets/js/6.b5c87a76.js"><link rel="prefetch" href="/assets/js/60.6089e8d9.js"><link rel="prefetch" href="/assets/js/61.2f20e8a2.js"><link rel="prefetch" href="/assets/js/62.03592460.js"><link rel="prefetch" href="/assets/js/63.77002dd4.js"><link rel="prefetch" href="/assets/js/64.9032ac20.js"><link rel="prefetch" href="/assets/js/66.f56322cc.js"><link rel="prefetch" href="/assets/js/67.b4720219.js"><link rel="prefetch" href="/assets/js/68.22b14d91.js"><link rel="prefetch" href="/assets/js/69.05d40a9b.js"><link rel="prefetch" href="/assets/js/7.b762b15a.js"><link rel="prefetch" href="/assets/js/70.58ee6b2e.js"><link rel="prefetch" href="/assets/js/71.c8c5e013.js"><link rel="prefetch" href="/assets/js/72.36050559.js"><link rel="prefetch" href="/assets/js/73.586878ae.js"><link rel="prefetch" href="/assets/js/74.249922dd.js"><link rel="prefetch" href="/assets/js/75.d2ec1b51.js"><link rel="prefetch" href="/assets/js/76.72fa47b7.js"><link rel="prefetch" href="/assets/js/77.63eb8e33.js"><link rel="prefetch" href="/assets/js/78.c551873e.js"><link rel="prefetch" href="/assets/js/79.dd1c3366.js"><link rel="prefetch" href="/assets/js/8.ce6b453e.js"><link rel="prefetch" href="/assets/js/80.3c1d3de0.js"><link rel="prefetch" href="/assets/js/81.0324d116.js"><link rel="prefetch" href="/assets/js/82.5d8ac119.js"><link rel="prefetch" href="/assets/js/83.6b6d94c4.js"><link rel="prefetch" href="/assets/js/84.142b2d74.js"><link rel="prefetch" href="/assets/js/85.63f77dcd.js"><link rel="prefetch" href="/assets/js/86.986eceed.js"><link rel="prefetch" href="/assets/js/87.b0ad936b.js"><link rel="prefetch" href="/assets/js/88.e74f9927.js"><link rel="prefetch" href="/assets/js/89.d8a1d85d.js"><link rel="prefetch" href="/assets/js/9.cee9094a.js"><link rel="prefetch" href="/assets/js/90.ba242523.js"><link rel="prefetch" href="/assets/js/91.25593ea0.js"><link rel="prefetch" href="/assets/js/92.2bf12b05.js"><link rel="prefetch" href="/assets/js/93.90e9d9cd.js"><link rel="prefetch" href="/assets/js/94.9483ee0f.js"><link rel="prefetch" href="/assets/js/95.613a2f80.js"><link rel="prefetch" href="/assets/js/96.3a67111e.js"><link rel="prefetch" href="/assets/js/97.5b13c18d.js"><link rel="prefetch" href="/assets/js/98.7fb9a2ea.js"><link rel="prefetch" href="/assets/js/99.81da5e8b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.3fffbd7d.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://cdn.jsdelivr.net/gh/cmty256/imgs-blog@main/logo/白云.38zbldnhh180.jpg" alt="ShuangChenYue" class="logo"> <span class="site-name can-hide">ShuangChenYue</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="CPP语言" class="dropdown-title"><!----> <span class="title" style="display:;">CPP语言</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/c5bdd8/" class="nav-link">Cpp之旅</a></li><li class="dropdown-item"><!----> <a href="/pages/279e62/" class="nav-link">Cpp专栏</a></li><li class="dropdown-item"><!----> <a href="/pages/801755/" class="nav-link">Effective_CPP</a></li><li class="dropdown-item"><!----> <a href="/pages/6b2468/" class="nav-link">muduo网络库</a></li><li class="dropdown-item"><!----> <a href="/pages/5f8c9f/" class="nav-link">Unix环境高级编程</a></li><li class="dropdown-item"><!----> <a href="/pages/3f1d21/" class="nav-link">Cpp提高编程</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="计算机基础" class="dropdown-title"><!----> <span class="title" style="display:;">计算机基础</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/7b1cb2/" class="nav-link">计算机网络</a></li><li class="dropdown-item"><!----> <a href="/pages/6048a8/" class="nav-link">操作系统</a></li><li class="dropdown-item"><!----> <a href="/pages/3b34ba/" class="nav-link">数据结构</a></li><li class="dropdown-item"><!----> <a href="/pages/412fe7/" class="nav-link">Linux</a></li><li class="dropdown-item"><!----> <a href="/pages/2dcfa1/" class="nav-link">算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="数据库" class="dropdown-title"><!----> <span class="title" style="display:;">数据库</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/efa3f2/" class="nav-link">基础篇</a></li><li class="dropdown-item"><!----> <a href="/pages/ccc445/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/pages/54616e/" class="nav-link">Redis</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="系统设计" class="dropdown-title"><!----> <span class="title" style="display:;">系统设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/793d0a/" class="nav-link">权限校验</a></li><li class="dropdown-item"><!----> <a href="/pages/73ddd7/" class="nav-link">设计模式</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="开发日常" class="dropdown-title"><!----> <span class="title" style="display:;">开发日常</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/71f6ae/" class="nav-link">Git知识总结</a></li><li class="dropdown-item"><!----> <a href="/pages/777b8a/" class="nav-link">nvm使用小结</a></li><li class="dropdown-item"><!----> <a href="/pages/ee770e/" class="nav-link">虚拟机固定 IP 地址</a></li><li class="dropdown-item"><!----> <a href="/pages/e472d1/" class="nav-link">随笔（持续更新）</a></li><li class="dropdown-item"><!----> <a href="/pages/411aa4/" class="nav-link">VScode 插件 CodeGeeX 使用教程</a></li><li class="dropdown-item"><!----> <a href="/pages/0d525d/" class="nav-link">KylinV10 将项目上传至 Github教程</a></li><li class="dropdown-item"><!----> <a href="/pages/ef40f0/" class="nav-link">KylinV10 安装 MySQL 教程（可防踩雷）</a></li><li class="dropdown-item"><!----> <a href="/pages/f8640c/" class="nav-link">个人博客代码推送教程</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端学习" class="dropdown-title"><!----> <span class="title" style="display:;">前端学习</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/99897f/" class="nav-link">HTML与CSS</a></li><li class="dropdown-item"><!----> <a href="/pages/51542d/" class="nav-link">JS学习</a></li><li class="dropdown-item"><!----> <a href="/pages/803f9d/" class="nav-link">Vue3入门</a></li><li class="dropdown-item"><!----> <a href="/pages/ca4cfb/" class="nav-link">Vue3进阶</a></li><li class="dropdown-item"><!----> <a href="/pages/50e8d3/" class="nav-link">黑马Vue3</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="项目笔记" class="dropdown-title"><!----> <span class="title" style="display:;">项目笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/08dfe9/" class="nav-link">ip_file_hook</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面经" class="dropdown-title"><!----> <span class="title" style="display:;">面经</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/d69946/" class="nav-link">虎牙C++技术面经</a></li><li class="dropdown-item"><!----> <a href="/pages/29251d/" class="nav-link">金山一面复习</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/fa256e/" class="nav-link">博客搭建</a></li><li class="dropdown-item"><!----> <a href="/pages/335531/" class="nav-link">网站收藏箱</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><!----> <nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="CPP语言" class="dropdown-title"><!----> <span class="title" style="display:;">CPP语言</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/c5bdd8/" class="nav-link">Cpp之旅</a></li><li class="dropdown-item"><!----> <a href="/pages/279e62/" class="nav-link">Cpp专栏</a></li><li class="dropdown-item"><!----> <a href="/pages/801755/" class="nav-link">Effective_CPP</a></li><li class="dropdown-item"><!----> <a href="/pages/6b2468/" class="nav-link">muduo网络库</a></li><li class="dropdown-item"><!----> <a href="/pages/5f8c9f/" class="nav-link">Unix环境高级编程</a></li><li class="dropdown-item"><!----> <a href="/pages/3f1d21/" class="nav-link">Cpp提高编程</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="计算机基础" class="dropdown-title"><!----> <span class="title" style="display:;">计算机基础</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/7b1cb2/" class="nav-link">计算机网络</a></li><li class="dropdown-item"><!----> <a href="/pages/6048a8/" class="nav-link">操作系统</a></li><li class="dropdown-item"><!----> <a href="/pages/3b34ba/" class="nav-link">数据结构</a></li><li class="dropdown-item"><!----> <a href="/pages/412fe7/" class="nav-link">Linux</a></li><li class="dropdown-item"><!----> <a href="/pages/2dcfa1/" class="nav-link">算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="数据库" class="dropdown-title"><!----> <span class="title" style="display:;">数据库</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/efa3f2/" class="nav-link">基础篇</a></li><li class="dropdown-item"><!----> <a href="/pages/ccc445/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/pages/54616e/" class="nav-link">Redis</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="系统设计" class="dropdown-title"><!----> <span class="title" style="display:;">系统设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/793d0a/" class="nav-link">权限校验</a></li><li class="dropdown-item"><!----> <a href="/pages/73ddd7/" class="nav-link">设计模式</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="开发日常" class="dropdown-title"><!----> <span class="title" style="display:;">开发日常</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/71f6ae/" class="nav-link">Git知识总结</a></li><li class="dropdown-item"><!----> <a href="/pages/777b8a/" class="nav-link">nvm使用小结</a></li><li class="dropdown-item"><!----> <a href="/pages/ee770e/" class="nav-link">虚拟机固定 IP 地址</a></li><li class="dropdown-item"><!----> <a href="/pages/e472d1/" class="nav-link">随笔（持续更新）</a></li><li class="dropdown-item"><!----> <a href="/pages/411aa4/" class="nav-link">VScode 插件 CodeGeeX 使用教程</a></li><li class="dropdown-item"><!----> <a href="/pages/0d525d/" class="nav-link">KylinV10 将项目上传至 Github教程</a></li><li class="dropdown-item"><!----> <a href="/pages/ef40f0/" class="nav-link">KylinV10 安装 MySQL 教程（可防踩雷）</a></li><li class="dropdown-item"><!----> <a href="/pages/f8640c/" class="nav-link">个人博客代码推送教程</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端学习" class="dropdown-title"><!----> <span class="title" style="display:;">前端学习</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/99897f/" class="nav-link">HTML与CSS</a></li><li class="dropdown-item"><!----> <a href="/pages/51542d/" class="nav-link">JS学习</a></li><li class="dropdown-item"><!----> <a href="/pages/803f9d/" class="nav-link">Vue3入门</a></li><li class="dropdown-item"><!----> <a href="/pages/ca4cfb/" class="nav-link">Vue3进阶</a></li><li class="dropdown-item"><!----> <a href="/pages/50e8d3/" class="nav-link">黑马Vue3</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="项目笔记" class="dropdown-title"><!----> <span class="title" style="display:;">项目笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/08dfe9/" class="nav-link">ip_file_hook</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面经" class="dropdown-title"><!----> <span class="title" style="display:;">面经</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/d69946/" class="nav-link">虎牙C++技术面经</a></li><li class="dropdown-item"><!----> <a href="/pages/29251d/" class="nav-link">金山一面复习</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/fa256e/" class="nav-link">博客搭建</a></li><li class="dropdown-item"><!----> <a href="/pages/335531/" class="nav-link">网站收藏箱</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>网络</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>操作系统</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>数据结构</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/2dcfa1/" class="sidebar-link">两数之和</a></li><li><a href="/pages/d52abe/" class="sidebar-link">最长公共前缀</a></li><li><a href="/pages/4c0819/" class="sidebar-link">删除有序数组中的重复项</a></li><li><a href="/pages/edd6da/" class="sidebar-link">最大子数组和</a></li><li><a href="/pages/480e04/" class="sidebar-link">x 的平方根</a></li><li><a href="/pages/6b01fc/" class="sidebar-link">爬楼梯</a></li><li><a href="/pages/3ec756/" class="sidebar-link">对称二叉树</a></li><li><a href="/pages/cfaacb/" class="sidebar-link">二叉树的最大深度</a></li><li><a href="/pages/5b2b9b/" class="sidebar-link">LCR寻找文件副本</a></li><li><a href="/pages/4e735a/" class="sidebar-link">买卖股票的最佳时机</a></li><li><a href="/pages/61a107/" class="sidebar-link">LCR图书整理 II</a></li><li><a href="/pages/d2368e/" class="sidebar-link">只出现一次的数字</a></li><li><a href="/pages/4806d9/" class="sidebar-link">LCR 训练计划 II</a></li><li><a href="/pages/6ac024/" class="sidebar-link">环形链表</a></li><li><a href="/pages/7c062a/" class="sidebar-link">反转链表</a></li><li><a href="/pages/28ad9f/" class="sidebar-link">翻转二叉树</a></li><li><a href="/pages/29ee33/" class="sidebar-link">回文链表</a></li><li><a href="/pages/e85eda/" class="sidebar-link">移动零</a></li><li><a href="/pages/5d801b/" class="sidebar-link">最长回文串</a></li><li><a href="/pages/55ec77/" class="sidebar-link">汉明距离</a></li><li><a href="/pages/299c79/" class="sidebar-link">把二叉搜索树转换为累加树</a></li><li><a href="/pages/6354db/" class="sidebar-link">最短无序连续子数组</a></li><li><a href="/pages/2998a0/" class="sidebar-link">合并二叉树</a></li><li><a href="/pages/173765/" class="sidebar-link">二分查找</a></li><li><a href="/pages/d178f3/" class="sidebar-link">链表的中间结点</a></li><li><a href="/pages/67ccea/" aria-current="page" class="active sidebar-link">有序数组的平方</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level2"><a href="/pages/67ccea/#题目" class="sidebar-link">题目：</a></li><li class="sidebar-sub-header level2"><a href="/pages/67ccea/#示例" class="sidebar-link">示例：</a></li><li class="sidebar-sub-header level2"><a href="/pages/67ccea/#解题" class="sidebar-link">解题：</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level3"><a href="/pages/67ccea/#方法一-直接排序" class="sidebar-link">方法一：直接排序</a></li><li class="sidebar-sub-header level3"><a href="/pages/67ccea/#方法二-双指针法" class="sidebar-link">方法二：双指针法</a></li><li class="sidebar-sub-header level3"><a href="/pages/67ccea/#方法三-双指针" class="sidebar-link">方法三：双指针</a></li></ul></li></ul></li><li><a href="/pages/33a1c0/" class="sidebar-link">找到小镇的法官</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>Linux</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"><div class="theme-vdoing-wrapper "><div class="articleInfo-wrap" data-v-06225672><div class="articleInfo" data-v-06225672><ul class="breadcrumbs" data-v-06225672><li data-v-06225672><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-06225672></a></li> <li data-v-06225672><span data-v-06225672>计算机基础</span></li><li data-v-06225672><span data-v-06225672>算法</span></li></ul> <div class="info" data-v-06225672><div title="作者" class="author iconfont icon-touxiang" data-v-06225672><a href="javascript:;" data-v-06225672>霜晨月</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-06225672><a href="javascript:;" data-v-06225672>2023-12-21</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-title">目录</div> <div class="right-menu-content"></div></div></div> <h1><img src="">有序数组的平方<!----></h1> <!----> <div class="theme-vdoing-content content__default"><h1 id="_977-有序数组的平方"><a href="#_977-有序数组的平方" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/squares-of-a-sorted-array/" target="_blank" rel="noopener noreferrer">977. 有序数组的平方<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h1> <h2 id="题目"><a href="#题目" class="header-anchor">#</a> 题目：</h2> <p>给你一个按 <strong>非递减顺序</strong> 排序的整数数组 <code>nums</code>，返回 <strong>每个数字的平方</strong> 组成的新数组，要求也按 <strong>非递减顺序</strong> 排序。</p> <h2 id="示例"><a href="#示例" class="header-anchor">#</a> 示例：</h2> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= nums.length &lt;= 104</code></li> <li><code>-104 &lt;= nums[i] &lt;= 104</code></li> <li><code>nums</code> 已按 <strong>非递减顺序</strong> 排序</li></ul> <p><strong>进阶：</strong></p> <ul><li>请你设计时间复杂度为 <code>O(n)</code> 的算法解决本问题</li></ul> <h2 id="解题"><a href="#解题" class="header-anchor">#</a> 解题：</h2> <h3 id="方法一-直接排序"><a href="#方法一-直接排序" class="header-anchor">#</a> 方法一：直接排序</h3> <p>最简单的方法就是将数组 nums 中的数平方后直接排序。</p> <div class="language-CPP line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">sortedSquares</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ans<span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> num <span class="token operator">:</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            ans<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>num <span class="token operator">*</span> num<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token function">sort</span><span class="token punctuation">(</span>ans<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span>ans<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br></div></div><p><strong>复杂度分析</strong></p> <p>时间复杂度：O(nlog⁡n)，其中 n 是数组 nums 的长度。</p> <p>空间复杂度：O(log⁡n)。除了存储答案的数组以外，我们需要 O(log⁡n) 的栈空间进行排序。</p> <h3 id="方法二-双指针法"><a href="#方法二-双指针法" class="header-anchor">#</a> 方法二：双指针法</h3> <p>方法一没有利用「数组 nums 已经按照升序排序」这个条件。显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。</p> <p>这样一来，如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。具体地，我们设 neg 为数组 nums 中负数与非负数的分界线，也就是说，nums[0] 到 nums[neg] 均为负数，而 nums[neg+1] 到 nums[n−1] 均为非负数。当我们将数组 nums 中的数平方后，那么 nums[0] 到 nums[neg] 单调递减，nums[neg+1] 到 nums[n−1] 单调递增。</p> <p>由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置 neg 和 neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。</p> <div class="language-CPP line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">sortedSquares</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> n <span class="token operator">=</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> negative <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                negative <span class="token operator">=</span> i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> ans<span class="token punctuation">;</span>
        <span class="token keyword">int</span> i <span class="token operator">=</span> negative<span class="token punctuation">,</span> j <span class="token operator">=</span> negative <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>i <span class="token operator">&gt;=</span> <span class="token number">0</span> <span class="token operator">||</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> 			<span class="token comment">// 说明数组没有负数</span>
                ans<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">*</span>nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">++</span>j<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>j <span class="token operator">==</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span>    <span class="token comment">// 说明数组全是负数</span>
                ans<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">*</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">--</span>i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">*</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">*</span>nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 数组有正有负，比较两边</span>
                ans<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">*</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">--</span>i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
                ans<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">*</span>nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">++</span>j<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br></div></div><p><strong>复杂度分析</strong></p> <ul><li><p>时间复杂度：O(n)，其中 n 是数组 nums 的长度。</p></li> <li><p>空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。</p></li></ul> <h3 id="方法三-双指针"><a href="#方法三-双指针" class="header-anchor">#</a> 方法三：双指针</h3> <p>同样地，我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。</p> <p>因此，对于前半部分负数而言，从前往后遍历，平方后相当于逆序（从大到小），对于后半部分正数而言，从后往前遍历，也相当于逆序（从大到小），因此，可以看成两个逆序数组数组从大到小排序，然后取较大者插入到答案数组尾部中。</p> <div class="language-CPP line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">sortedSquares</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> n <span class="token operator">=</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">ans</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> j <span class="token operator">=</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> pos <span class="token operator">=</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> j<span class="token punctuation">;</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">*</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&gt;</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">*</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
                ans<span class="token punctuation">[</span>pos<span class="token punctuation">]</span> <span class="token operator">=</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">*</span> nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
                <span class="token operator">++</span>i<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span> <span class="token punctuation">{</span>
                ans<span class="token punctuation">[</span>pos<span class="token punctuation">]</span> <span class="token operator">=</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">*</span> nums<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
                <span class="token operator">--</span>j<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token operator">--</span>pos<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br></div></div><p><strong>复杂度分析</strong></p> <ul><li><p>时间复杂度：O(n)，其中 n 是数组 nums 的长度。</p></li> <li><p>空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。</p></li></ul></div></div> <!----> <div class="page-edit"><!----> <!----> <!----></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/d178f3/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">链表的中间结点</div></a> <a href="/pages/33a1c0/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">找到小镇的法官</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/d178f3/" class="prev">链表的中间结点</a></span> <span class="next"><a href="/pages/33a1c0/">找到小镇的法官</a>→
      </span></p></div></div></div> <!----></main></div> <div class="footer"><!----> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2023-2023
    <span>霜晨月</span></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div> <div title="主题模式" class="button blur theme-mode-but iconfont icon-zhuti"><ul class="select-box" style="display:none;"><li class="iconfont icon-zidong">
          跟随系统
        </li><li class="iconfont icon-rijianmoshi">
          浅色模式
        </li><li class="iconfont icon-yejianmoshi">
          深色模式
        </li><li class="iconfont icon-yuedu">
          阅读模式
        </li></ul></div></div> <!----> <!----> <!----></div><div class="global-ui"><canvas id="vuepress-canvas-cursor"></canvas></div></div>
    <script src="/assets/js/app.c23950b3.js" defer></script><script src="/assets/js/2.4615a819.js" defer></script><script src="/assets/js/65.1a70901c.js" defer></script>
  </body>
</html>
